/**
 * Universidad Del Valle De Guatemala.
 * Algoritmos y Estructuras de Datos.
 * Sección 20.
 * Miguel Enrique Zea Arenales.
 * Carné 09238.
 * 20/09/2012.
 */
package heapshuffman;

import java.lang.Math;

/**
 * @author Miguel Zea
 * Implementación de un nodo de la estructura recursiva denominada árbol binario.
 * Tomado del texto Java Structures de Duane A. Bailey capítulo 12.
 * http://www.cs.williams.edu/JavaStructures/Book.html
 */
public class BinaryTree<E> {
    protected E val; // Valor asociado al nodo.
    protected BinaryTree<E> parent; // Referencia al nodo padre.
    protected BinaryTree<E> left, right; // Referencia a los nodos hijos (izquierdo y derecho).

    /**
     * @pre Ninguna.
     * @post Constructor que genera un nodo vacío.
     */
    public BinaryTree() {
        val = null;
        parent = null; left = right = this;
    }

    /**
     * @pre Ninguna.
     * @post Construye un árbol de sólo un nodo, sin ningún nodo hijo, con un
     * valor asociado.
     */
    public BinaryTree(E value) {
        assert(value != null);
        val = value;
        right = left = new BinaryTree<E>();
        setLeft(left);
        setRight(right);
    }

    /**
     * @pre Ninguna.
     * @post Construye un nodo (con un valor especificado) de árbol binario con dos hijos.
     */
    public BinaryTree(E value, BinaryTree<E> left, BinaryTree<E> right) {
        assert(value != null);
        val = value;
        if (left == null) { left = new BinaryTree<E>(); }
        setLeft(left);
        if (right == null) { right = new BinaryTree<E>(); }
        setRight(right);
    }

    /**
     * @pre Ninguna.
     * @post Regresa la referencia al sub-árbol izquierdo del nodo actual.
     */
    public BinaryTree<E> left() {
        return left;
    }

    
    /**
     * @pre Ninguna.
     * @post Regresa la referencia al sub-árbol derecho del nodo actual.
     */
    public BinaryTree<E> right() {
        return right;
    }

    /**
     * @pre Ninguna.
     * @post Regresa la referencia al padre del nodo actual.
     */
    public BinaryTree<E> parent() {
        return parent;
    }
    
    /**
     * @pre El nuevo sub-árbol izquierdo es no nulo.
     * @post Actualiza el sub-árbol izquierdo del nodo actual para que referencie
     * al indicado por el parámetro.
     */
    public void setLeft(BinaryTree<E> newLeft) {
        if (isEmpty()) return;
        if (left != null && left.parent() == this) left.setParent(null);
        left = newLeft;
        left.setParent(this);
    }

    /**
     * @pre El nuevo sub-árbol derecho es no nulo.
     * @post Actualiza el sub-árbol derecho del nodo actual para que referencie
     * al indicado por el parámetro.
     */
    public void setRight(BinaryTree<E> newRight) {
        if (isEmpty()) return;
        if (right != null && right.parent() == this) right.setParent(null);
        right = newRight;
        right.setParent(this);
    }

    /**
     * @pre El nuevo padre es no nulo.
     * @post Actualiza el padre del nodo actual para que referencie al indicado 
     * por el parámetro.
     */
    protected void setParent(BinaryTree<E> newParent) {
        if (!isEmpty()) {
            parent = newParent;
        }
    }

    /**
     * @pre Ninguna.
     * @post Regresa el tamaño del sub-árbol.
     */
    public int size() {
        if (isEmpty()) return 0;
        return left().size() + right().size() + 1;
    }

    /**
     * @pre Ninguna.
     * @post Regresa la referencia a la raíz del árbol en donde se encuentra
     * contenido el nodo.
     */
    public BinaryTree<E> root() {
        if (parent() == null) return this;
        else return parent().root();
    }

    /**
     * @pre Ninguna.
     * @post Regresa la altura del nodo en el árbol, siendo ésta el máximo camino
     * hacia un descendiente.
     */
    public int height() {
        if (isEmpty()) return -1;
        return 1 + Math.max(left.height(), right.height());
    }

    /**
     * @pre Ninguna.
     * @post Regresa la profundidad del nodo en el árbol, siendo ésta el camino
     * desde la raíz hasta el nodo.
     */
    public int depth() {
        if (parent() == null) return 0;
        return 1 + parent.depth();
    }

    /**
     * @pre Ninguna.
     * @post Regresa verdadero si el árbol está lleno, es decir, si añadir un 
     * nodo necesariamente incrementa su altura.
     */
    public boolean isFull() {
        if (isEmpty()) return true;
        if (left().height() != right().height()) return false;
        return left().isFull() && right().isFull();
    }

    /**
     * @pre Ninguna.
     * @post Regresa verdadero si el árbol con raíz en el nodo está vacío.
     */
    public boolean isEmpty() {
        return val == null;
    }
    
    /**
     * @pre Ninguna.
     * @post Regresa verdadero si el nodo actual es el hijo izquierdo de su padre.
     */
    public boolean isLeftChild() {
        if (parent() == null) return false;
        return this == parent().left();
    }

    /**
     * @pre Ninguna.
     * @post Regresa verdadero si el nodo actual es el hijo derecho de su padre.
     */
    public boolean isRightChild() {
        if (parent() == null) return false;
        return this == parent().right();
    }

    /**
     * @pre Ninguna.
     * @post Regresa el valor asociado al nodo.
     */
    public E value() {
        return val;
    }

    /**
     * @pre Ninguna.
     * @post Establece el valor asociado al nodo.
     */
    public void setValue(E value) {
        val = value;
    }
}

